\section{Conclusion}\label{sec:conc}
We presented fast and fully decentralized algorithms for performing  random walks in distributed dynamic networks. Our algorithm satisfies strong round complexity guarantees and our work presents robust techniques for this fundamental graph primitive in dynamic graphs.
 We further extend the work to show how it can be used for efficient sampling and other applications such as token dissemination. Our bounds for the token dissemination problem improve on previously best known algorithms under a suitably general dynamic graph  model. 
 Our framework and results have also
 been used subsequently in other dynamic network applications as well \cite{storage-spaa13, APR-podc13}.
 
Our work opens several interesting research directions. 
 In the recent years, several fundamental graph operatives are being explored in various distributed dynamic models, and it would be interesting to explore further along these lines and obtain new approaches for identifying sparse cuts or graph partitioning, and similar spectral quantities. 
 
As a specific question, it remains open whether the random walk techniques and subsequent bounds presented in this paper are optimal.  Our random walk algorithm requires knowledge of $\tau$ and $\Phi$ to get the claimed running time of $\tilde{O}(\sqrt{\tau\Phi})$; it will be good
to design an algorithm that works even without this knowledge. Another open question is to extend our algorithm for more realistic dynamic network models, e.g., one that involves
nodes joining or leaving the network \cite{storage-spaa13,APR-podc13,JGPE:soda12,sirocco14}. Also, it will be interesting to extend our algorithm to work without knowledge
of upper bound on degree (assuming that the degrees vary quite a bit).
Another fundamental question is whether we can better  bounds for  the information dissemination problem in the oblivious adversary model that is considered here. Our protocol is faster than the naive protocol only in restricted settings. It will
be interesting to build on this work and show protocols that can be faster in more general settings.
  
 Finally, these algorithmic ideas may be useful building blocks in designing fully dynamic self-aware distributed graph systems (where random walk techniques are helpful \cite{ZS06}). 
 It would be interesting to additionally consider total message complexity costs for these algorithms explicitly, even though they are implicitly encapsulated within the local per-edge bandwidth constraints of the CONGEST model. 
 
 \section*{Acknowledgments}
We thank the anonymous reviewers  for their detailed comments which helped in improving the presentation
of the paper.

\endinput